
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
        return null;
        }

        if(root == p || root == q) {
        return root;
        }

        TreeNode leftT = lowestCommonAncestor(root.left,p,q);
        TreeNode rightT = lowestCommonAncestor(root.right,p,q);

        if(leftT != null && rightT != null) {
        return root;
        }else if(leftT != null) {
        return leftT;
        }else {
        return rightT;
        }
        }


public boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack) {
        if(root == null || node == null) return false;
        stack.push(root);
        if(root == node) return true;
        boolean flg = getPath(root.left,node,stack);
        if(flg) {
        return true;
        }
        flg = getPath(root.right,node,stack);
        if(flg) {
        return true;
        }
        stack.pop();
        return false;
        }

public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        Stack<TreeNode> stack1 = new Stack<>();
        getPath(root,p,stack1);
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root,q,stack2);

        int size1 = stack1.size();
        int size2 = stack2.size();
        if(size1 > size2) {
        int size = size1-size2;
        while( size != 0) {
        //出第一个栈里面的元素
        stack1.pop();
        size--;
        }
        while(!stack1.isEmpty() && !stack2.isEmpty()) {
        //判断地址
        if(stack1.peek() == stack2.peek()) {
        return stack1.pop();
        }else{
        stack1.pop();
        stack2.pop();
        }
        }
        }else{
        int size = size2-size1;
        while( size != 0) {
        //出第一个栈里面的元素
        stack2.pop();
        size--;
        }
        while(!stack1.isEmpty() && !stack2.isEmpty()) {
        //判断地址
        if(stack1.peek() == stack2.peek()) {
        return stack1.pop();
        }else{
        stack1.pop();
        stack2.pop();
        }
        }
        }
        return null;
        }
public class ZuoYe0825 {


}
